Инкременталност
Једна од основних техника за избегавање лоше сложености алгоритама је да се избегне израчунавање истих ствари више пута у истом програму. Често је потребно израчунати неку вредност за различите вредности неког параметра. Рећи ћемо да је израчунавање инкрементално ако се резултујућа вредност за наредну вредност параметра израчунава коришћењем већ израчунатих вредности за претходну (или неколико претходних) вредности параметра. Дакле, на мале измене улазних података реагујемо малим изменама резултата (уместо да поново вршимо велико израчунавање свега, из почетка).
Веома једноставан пример принципа инкременталности је израчунавање парцијалних збирова (збирови префикса) елемената неког низа. На пример, ако је дат низ \(1, 2, 3, 4, 5\), његови парцијални збирови су редом \(0, 1, 3, 6, 10, 15\). Веома једноставно се примећује да се израчунавање наредног парцијалног збира не мора вршити сабирањем свих елемената од почетка, већ се може добити сабирањем претходног парцијалног збира са текућим елементом низа (на пример, збир \(1+2+3+4 = 10\), се добија сабирањем претходног збира \(1+2+3 = 6\) и текућег елемента \(4\)). Ако збир првих \(k\) елемената означимо са \(Z_k\), тада важи да је \(Z_0 = 0\) и да је \(Z_{k+1} = Z_k + a_k\). Овим смо добили серију бројева у којој се наредни елемент израчунава на основу претходног (или неколико претходних). За такве серије кажемо да су рекурентне серије. Сваки наредни члан се израчунава у сложености \(O(1)\), па се израчунавање свих парцијалних збирова низа дужине \(n\) врши у сложености \(O(n)\). Када би се сваки парцијални збир рачунао сабирањем елемената низа из почетка, тада би израчунавање \(k\)-тог збира било сложености \(O(k)\), а израчунавање свих збирова сложености \(O(n^2)\).
Принцип инкременталности је у тесној вези са индуктивно/рекурзивном конструкцијом алгоритама и лежи у основи великог броја основних алгоритама. Већ само израчунавање збира свих елемената низа заправо почива на постепеном, инкременталном израчунавању збирова префикса, све док се не израчуна збир свих елемената низа. Слично је и са израчунавањем минумума, максимума, линеарном претрагом и другим фундаменталним алгоритмима. У свим овим примерима крећемо од неке почетне вредности у низу резултата, а затим наредну вредност у том низу израчунавамо на основу претходне или неколико претходних, што директно одговара индуктивном поступку израчунавања. Слична техника (добијања наредних резултата на основу претходних) примењује се у склопу технике динамичког програмирања навише, о чему ће више речи бити касније.
Поред парцијалних збирова, инкрементално се могу израчунавати и парцијални производи, парцијални минимуми и максимуми и слично.